1 课程大纲

1.2 二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？

1.3 树

“高度”这个概念，其实就是从下往上度量，比如我们要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。

“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。

“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点的位于第 1 层。

高度———> 边树

深度———-> 根结点到这个节点的边的个数

1.3 二叉树Binary Tree

1.4 如何表示（或者存储）一棵二叉树？

我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

链式存储法

每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

顺序存储法。

我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

我来总结一下，如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
当我们讲到堆和堆排序的时候，你会发现，堆其实就是一种完全二叉树，最常用的存储方式就是数组。

1.5 二叉树的遍历

前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。(根左右)
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

（左根右）
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。（左右根）

实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。

****二叉树遍历的时间复杂度是 O(n)。

2 二叉树实现代码

静态创建二叉树

上面说了，树是由若干个节点组成，节点连接起来就成了树，而节点由一个数据、两个指针组成

因此，创建树实际上就是创建节点，然后连接节点


public class TreeNode {

    //左节点（儿子）
    private TreeNode leftNode;
    //右节点
    private TreeNode rightNode;

    private int value;
    
    public TreeNode(int value) {

        this.value = value;
    }
    
    
    public static void main(String[] args) {

        //根节点-->10
        TreeNode treeNode1 = new TreeNode(10);

        //左孩子-->9
        TreeNode treeNode2 = new TreeNode(9);

        //右孩子-->20
        TreeNode treeNode3 = new TreeNode(20);
        
        //20的左孩子-->15
        TreeNode treeNode4 = new TreeNode(15);
        
        //20的右孩子-->35
          TreeNode treeNode5 = new TreeNode(35)        
       //根节点的左右孩子
  	    	 treeNode1.setLefTreeNode(treeNode2);
   	    	 treeNode1.setRightNode(treeNode3);

   			 //20节点的左右孩子
   				 treeNode3.setLefTreeNode(treeNode4);
   				 treeNode3.setRightNode(treeNode5);
    }
}

1.3遍历二叉树

上面说我们的树创建完成了，那怎么证明呢？？我们如果可以像数组一样遍历它(看它的数据)，那就说明它创建完成了～

值得说明的是：二叉树遍历有三种方式

先序遍历
- 先访问根节点，然后访问左节点，最后访问右节点(根->左->右)
中序遍历
- 先访问左节点，然后访问根节点，最后访问右节点(左->根->右)
后序遍历
- 先访问左节点，然后访问右节点，最后访问根节点(左->右->根)

以上面的二叉树为例：

如果是先序遍历：10->9->20->15->35
如果是

中序遍历

：
1
9->10->15->20->35
- 可能需要解释地方：访问完10节点过后，去找的是20节点，但20下还有子节点，因此先访问的是20的左儿子15节点。由于15节点没有儿子了。所以就返回20节点，访问20节点。最后访问35节点
如果是

后序遍历

：
1
9->15->35->20->10
- 可能需要解释地方：先访问9节点，随后应该访问的是20节点，但20下还有子节点，因此先访问的是20的左儿子15节点。由于15节点没有儿子了。所以就去访问35节点，由于35节点也没有儿子了，所以返回20节点，最终返回10节点

一句话总结：先序(根->左->右)，中序(左->根->右)，后序(左->右->根)。如果访问有孩子的节点，先处理孩子的，随后返回

无论先中后遍历，每个节点的遍历如果访问有孩子的节点，先处理孩子的(逻辑是一样的)

因此我们很容易想到递归
递归的出口就是：当没有子节点了，就返回

因此，我们可以写出这样的先序遍历代码：

/**
 * 先序遍历
 * @param rootTreeNode  根节点
 */
public static void preTraverseBTree(TreeNode rootTreeNode) {

    if (rootTreeNode != null) {

        //访问根节点
        System.out.println(rootTreeNode.getValue());

        //访问左节点
        preTraverseBTree(rootTreeNode.getLefTreeNode());

        //访问右节点
        preTraverseBTree(rootTreeNode.getRightNode());
    }
}

结果跟我们刚才说的是一样的：

我们再用中序遍历调用一遍吧：

/**
 * 中序遍历
 * @param rootTreeNode  根节点
 */
public static void inTraverseBTree(TreeNode rootTreeNode) {

    if (rootTreeNode != null) {

        //访问左节点
        inTraverseBTree(rootTreeNode.getLefTreeNode());

        //访问根节点
        System.out.println(rootTreeNode.getValue());

        //访问右节点
        inTraverseBTree(rootTreeNode.getRightNode());
    }
}